package hot;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Num56 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        List<int[]> res = new ArrayList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int i = 0; i < intervals.length - 1; i++) {
            if(end >= intervals[i + 1][0]) {
                end = Math.max(intervals[i + 1][1],end);
            }else {
                int[] arr = new int[]{start,end};
                res.add(arr);
                start = intervals[i + 1][0];
                end = intervals[i + 1][1];
            }
        }
        int[] arr = new int[]{start,end};
        res.add(arr);
        int n = res.size();
        int[][] nums = new int[n][2];
        for(int i = 0; i < n; i++) {
            int[] array = res.get(i);
            nums[i][0] = array[0];
            nums[i][1] = array[1];
        }
        return nums;
    }
}
